class Solution
{
public:
    vector<int> preorderTraversal(TreeNode *root)
    {
        stack<TreeNode *> st;
        vector<int> ans;
        while (root || !st.empty())
        {
            while (root)
            {
                ans.push_back(root->val);
                st.push(root);
                root = root->left;
            }
            // 循环结束，左节点遍历结束
            root = st.top()->right;
            st.pop();
        }
        return ans;
    }
};

class Solution
{
public:
    vector<int> inorderTraversal(TreeNode *root)
    {
        // 与前序同样的思想
        // 不同的是这次在放栈顶的时候根不能放进去
        stack<TreeNode *> st;
        // stack<int> st1;
        vector<int> ans;
        while (root || !st.empty())
        {
            while (root)
            {
                st.push(root);
                root = root->left;
            }
            ans.push_back(st.top()->val);
            root = st.top()->right;
            st.pop();
        }
        return ans;
    }
};

class Solution
{
public:
    vector<int> postorderTraversal(TreeNode *root)
    {
        stack<TreeNode *> st;
        TreeNode *prev = nullptr;
        vector<int> ans;
        while (root || !st.empty())
        {
            while (root)
            {
                st.push(root);
                root = root->left;
            }
            TreeNode *tmp = st.top();
            // 如果该节点右树为空，则直接访问
            // 根据后序遍历的特点，如果当前节点需要访问
            // 那么前一个访问的节点一定是该节点的右子树的根
            if (tmp->right == nullptr || prev == tmp->right)
            {
                prev = tmp;
                ans.push_back(tmp->val);
                st.pop();
            }
            else
                root = tmp->right;
        }
        return ans;
    }
};